package org.myy.learn.hot.贪心算法;

import lombok.extern.slf4j.Slf4j;

@Slf4j
public class 跳跃游戏Ⅱ {
    public static int jump(int[] nums) {
        int n = nums.length;
        int end = 0; //标记能到达的最远点
        int rightmost = 0;
        int step = 0;
        for (int i=0; i < n-1;i++){
            rightmost = Math.max(rightmost, i+nums[i]);
            if (i == end){ //达到标记的最远点，让后跳一步
                end = rightmost;
                step++;
            }
        }
        return step;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{2,3,1,1,4};
        int jump = jump(nums);
        log.info("执行结束，jump={}", jump);
    }
}
